//
//  8.跳台阶.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/17.
//

import Foundation
/*
 题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
 思路：⾸先我们考虑最简单的情况。如果只有1级台阶，那么显然只⼀种跳法。如果有2级台阶，那就有两种跳法：⼀种是分两次跳，每次跳1级；另⼀种是⼀ 次跳2级。 接着，我们来讨论⼀般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。当n>2时，第⼀次跳的时候就有两种不同的选择：⼀是第⼀次只跳1 级，此时跳法数⽬等于后⾯剩下的n-1级台阶的跳法数⽬，即为f(n-1)；另外⼀种选择是跳⼀次跳2级，此时跳法数⽬等于后⾯剩下的n-2级台阶的跳法数⽬， 即为f(n-2)。因此n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2)。分析到这⾥，我们不难看出这实际上就是斐波那契数列了。（动态规划）
 */
func offer_8() {
    print(Solution().jumpFloor(4))
}

fileprivate class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param n int整型
     * @return int整型
     */
    func jumpFloor(_ n: Int) -> Int {
        // write code here
        guard n > 2 else { return n }
        var first = 1
        var second = 2
        var num: Int = 0
        for _ in 3...n {
            num = first + second
            first = second
            second = num
        }
        return num
    }
}
